package 系统复习.动态规划;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 分析步骤
 * 1、dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法
 * 2、dp[i] = dp[i - 1] + dp[i - 2]
 * 3、dp[1] = 1，dp[2] = 2
 * 4、从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
 */
public class L70 {

    public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1;
        int b = 2;
        int result = 0;
        for (int i = 3; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }



    public static void main(String[] args) {
        L70 l70 = new L70();
        System.out.println(l70.climbStairs(44));
    }
}
